package 每日一题;

import common.GeneralFunction;

import java.util.Arrays;

public class No5最长回文子串 {

    /**
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     *
     * 示例 1：
     * 输入：s = "babad"
     * 输出："bab"
     * 解释："aba" 同样是符合题意的答案。
     * 示例 2：
     * 输入：s = "cbbd"
     * 输出："bb"
     * 示例 3：
     * 输入：s = "a"
     * 输出："a"
     */

    /**
     * 动态规划法
     */
    public String longestPalindrome(String s) {

        if(s.length()==1){
            return s;
        }

        int[][] dp=new int[s.length()][s.length()];

        //base
        for (int i = 0; i < s.length(); i++) {
            dp[i][i]=1;
        }

        int rLeft=0;
        int rRight=0;
        int maxLength=1;
        //开始dp
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < i; j++) {
                dp[i][j]=1;//base
                if(s.charAt(i)==s.charAt(i-1)&&2>dp[i][j]){
                    if(maxLength<2) {
                        maxLength = 2;
                        rLeft = i - 1;
                        rRight = i;
                    }
                    dp[i][j]=2;
                }
                if(j+1<s.length()) {
                    int count = dp[i - 1][j + 1];
                    if (count != 0) {
                        //可以进行比较
                        int right = i;
                        int left = i - 1 - count;
                        if (left >= 0 && s.charAt(left) == s.charAt(right)) {
                            dp[i][j] = count + 2;
                        }
                        if (dp[i][j] > maxLength) {
                            maxLength = dp[i][j];
                            rLeft = left;
                            rRight = right;
                        }
                    }
                }
            }
        }

        return s.substring(rLeft,rRight+1);
    }

    public String longestPalindromeGood(String s) {

        if(s.length()==1){
            return s;
        }

        /**
         * 精髓方法:
         * dp[]->[i..j]是否为回文子串
         */
        boolean[][] dp=new boolean[s.length()][s.length()];

        //base
        for (int i = 0; i < s.length(); i++) {
            dp[i][i]=true;
        }

        //最长
        int maxLength=1;
        //最长的起始位
        int beginIndex=0;

        for (int i = 2; i <= s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {

                int left=j;
                int right=j+i-1;
                if(right>=s.length()){
                    break;
                }
                if(s.charAt(left)==s.charAt(right)){
                    //相等
                    if(right-left<=2){
                        //2长 或者 3长
                        dp[left][right]=true;
                    }else{
                        //4长及其以上 假设 0 1 2 3 现 0,3相等 就需要判断 0+1和3-1是否相等
                        dp[left][right]=dp[left+1][right-1];
                    }
                }else{
                    //不相等就什么都不做
                }

                if(dp[left][right]&&right-left+1>maxLength){
                    maxLength=right-left+1;
                    beginIndex=left;
                }

            }
        }

        return s.substring(beginIndex,beginIndex+maxLength);
    }

    /**
     * 中心扩散法
     */
    private char[] ch;
    private String str;
    public String longestPalindromeGood2(String s){
        if(s==null){
            return null;
        }
        if(s.length()==0){
            return "";
        }
        this.str=s;
        this.ch=s.toCharArray();
        int maxLeft=0;
        int maxRight=1;

        //最后一个字符无需校验
        for (int i = 0; i < s.length()-1; i++) {
            int[] arr1 = isPalindromeVerification2(i, i);
            if(arr1[1]-arr1[0]>=maxRight-maxLeft){
                maxRight=arr1[1]+1;
                maxLeft=arr1[0];
            }
            int[] arr2 = isPalindromeVerification2(i, i + 1);
            if(arr2[1]-arr2[0]>=maxRight-maxLeft){
                maxRight=arr2[1]+1;
                maxLeft=arr2[0];
            }
        }

        return s.substring(maxLeft,maxRight);
    }

    private int[] isPalindromeVerification2(int left,int right){

        while (left>=0&&right<str.length()){

            if(ch[left]==ch[right]){
                left--;
                right++;
            }else{
                break;
            }
            //会白加一个
            if(left==-1){
                return new int[]{0,right-1};
            }
            if(right==str.length()){
                return new int[]{left+1,str.length()-1};
            }
        }
        return new int[]{left+1,right-1};
    }

    public static void main(String[] args) {
        No5最长回文子串 n=new No5最长回文子串();
        String str="xaabacxcabaaxcabaax";
        String result = n.longestPalindrome(str);
        System.out.println(result);
        System.out.println(n.longestPalindromeGood(str));
    }

}
